package mylab.starters.dag.utils;

import com.google.common.base.Joiner;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

import cn.hutool.core.collection.CollUtil;
import lombok.experimental.UtilityClass;
import lombok.extern.slf4j.Slf4j;
import mylab.starters.dag.graph.Edge;
import mylab.starters.dag.graph.Graph;
import mylab.starters.dag.graph.Vertex;

@Slf4j
@UtilityClass
public class DagUtil {

    public void printDagPath(Graph graph) {
        printDagIndegree(graph);
        log.info("### graph path start ###");
        printDagPath(null, graph.getBeginVertices());
        log.info("### graph path end ###");
    }

    public void printDagIndegree(Graph graph) {
        Map<String, AtomicInteger> map = graph.getVertices().stream().collect(Collectors.toMap(Vertex::getId, Vertex::getIndegree));
        log.info("graph vertex indegree: {}", Joiner.on(",").withKeyValueSeparator("=").join(map));
    }

    void printDagPath(Vertex begin, Set<Vertex> vertices) {
        if (CollUtil.isEmpty(vertices)) {
            log.info("{} ---> {}", begin == null ? "begin" : begin.getName(), "end");
        } else {
            vertices.forEach(vertex -> {
                log.info("{} ---> {}", begin == null ? "begin" : begin.getName(), vertex.getName());
                printDagPath(vertex, vertex.getAdjacentVertices());
            });
        }
    }


    /**
     * 拓扑排序是将DAG图中的所有节点排成一个线性序列，使得对于每一条有向边(u, v)，节点u在序列中都出现在节点v的前面
     */
    public List<Vertex> topologicalSort(Graph dag) {
        Set<Vertex> vertices = dag.getVertices();
        Set<Edge> edges = dag.getEdges();

        Map<Vertex, Integer> inDegree = Maps.newHashMap();
        for (Vertex vertex : vertices) {
            inDegree.put(vertex, 0);
        }
        for (Edge edge : edges) {
            inDegree.put(edge.getTo(), inDegree.get(edge.getTo()) + 1);
        }
        Queue<Vertex> queue = new LinkedList<>();
        for (Map.Entry<Vertex, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.add(entry.getKey());
            }
        }

        List<Vertex> result = Lists.newArrayList();
        while (!queue.isEmpty()) {
            Vertex vertex = queue.poll();
            result.add(vertex);
            for (Vertex adjacent : vertex.getAdjacentVertices()) {
                inDegree.put(adjacent, inDegree.get(adjacent) - 1);
                if (inDegree.get(adjacent) == 0) {
                    queue.add(adjacent);
                }
            }
        }
        if (result.size() != vertices.size()) {
            throw new RuntimeException("Graph has a cycle!");
        }
        return result;
    }

    /**
     * 检查DAG图有无形成环
     * 使用深度优先搜索（DFS）来检查环的存
     */
    public boolean hasCycle(Collection<Vertex> vertices) {
        Set<Vertex> visited = new HashSet<>();
        Set<Vertex> recStack = new HashSet<>();
        for (Vertex vertex : vertices) {
            if (hasCycle(vertex, visited, recStack)) {
                return true;
            }
        }
        return false;
    }

    private boolean hasCycle(Vertex vertex, Set<Vertex> visited, Set<Vertex> recStack) {
        if (recStack.contains(vertex)) {
            return true;
        }
        if (visited.contains(vertex)) {
            return false;
        }
        visited.add(vertex);
        recStack.add(vertex);
        for (Vertex adjacent : vertex.getAdjacentVertices()) {
            if (hasCycle(adjacent, visited, recStack)) {
                return true;
            }
        }
        recStack.remove(vertex);
        return false;
    }
}
